import java.util.Comparator;
import java.util.PriorityQueue;

public class Top_K {
    public int[] smallestK(int[] arr, int k) {
        int[] arr2 = new int[k];

        if (k == 0 || arr.length == 0) {
            return arr2;
        }

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        for (int i : arr) {
            priorityQueue.offer(i);
        }

        for (int i = 0; i < k; i++) {
            arr2[i] = priorityQueue.poll();
        }

        return arr2;
    }

    public int[] smallestK1(int[] arr, int k) {
        int[] arr2 = new int[k];

        if (k == 0 || arr.length == 0) {
            return arr2;
        }

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCam());

        int i = 0;
        for ( ; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }

        for (int j = i; j < arr.length; j++) {
            if (priorityQueue.peek() > arr[j]) {
                priorityQueue.poll();
                priorityQueue.offer(arr[j]);
            }
        }

        for (i = 0; i < k; i++) {
            arr2[i] = priorityQueue.poll();
        }

        return arr2;
    }
}

class IntCam implements Comparator<Integer> {
    public int compare(Integer i, Integer j) {
        return j.compareTo(i);
    }
}
